class Solution:
    def search(self, nums: List[int], target: int) -> int:
        if not nums or nums[-1] < target or nums[0]>target:
            return -1
        left = 0
        right = len(nums)
        while left <= right:
            mid = (left+right)//2
            if nums[mid] >target:
                right = mid -1
            elif nums[mid] < target:
                left = mid +1
            else:
                return mid
        return -1